#include <vector>
#include <iostream>
using namespace std;


//version 1 
class Solution{
public:
    int Get(const vector<int>& nums){
        int left = 0, right = nums.size() - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[right] - nums[mid] == right - mid) right = mid;
            else left = mid + 1;
        }
        //出来就是left == right
        return (nums[left] - 1) == -1 ? nums[nums.size() - 1] + 1 : nums[left] - 1;
    }
};


//测试 因为在Leetcode上我是搜不到的！
int main(){
    cout << Solution().Get({0,1,2,3,4,5,6,7,8,9}) << endl;
    cout << Solution().Get({0,1,3}) << endl;
    cout << Solution().Get({0,1,2,3,4,5,6,7,9}) << endl;

    return 0;
}